#include <bits/stdc++.h>
using namespace std;

/*
1857. 有向图中最大颜色值
已解答
困难
相关标签
相关企业
提示
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。

给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。

图中一条有效 路径 是一个点序列 x1 -> x2 -> x3 -> ... -> xk ，对于所有 1 <= i < k ，从 xi 到 xi+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。

请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。

 

示例 1：



输入：colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
输出：3
解释：路径 0 -> 2 -> 3 -> 4 含有 3 个颜色为 "a" 的节点（上图中的红色节点）。
示例 2：



输入：colors = "a", edges = [[0,0]]
输出：-1
解释：从 0 到 0 有一个环。
 

提示：

n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors 只含有小写英文字母。
0 <= aj, bj < n
*/

// 法一
class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> adj(n); // 邻接表
        vector<int> inDegree(n, 0); // 入度表
        vector<vector<int>> dp(n, vector<int>(26, 0));  // dp[i][j] 以i结尾的路径中颜色j的最大数
        // 构建邻接表和入度表
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].push_back(v);
            inDegree[v]++;
        }
        // 队列
        queue<int> q;
        // 入度为0的节点加入队列
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0)   q.push(i);
        }

        // 访问过的 拓扑排序
        int visited = 0;
        int maxColor = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();        
            visited++;
            // 当前节点的颜色计数 +1
            int color = colors[u] - 'a';
            dp[u][color]++;
            maxColor = max(maxColor, dp[u][color]);
            // 更新邻接节点的dp值
            for (int v : adj[u]) {
                for (int ch = 0; ch < 26; ++ch) {
                    dp[v][ch] = max(dp[v][ch], dp[u][ch]);
                }
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        // 环状 -1
        if (visited != n) {
            return -1;
        }
        return maxColor;
    }
};

// 法二
class Solution {
    #define MAXN 100003 // 定义最大节点数
    int topsortarr[MAXN]; // 存储拓扑排序后的节点顺序
    int cnttop=0; // 记录拓扑排序的节点数量
    int dp[MAXN]; // 动态规划数组，记录当前路径中某个颜色的最大出现次数
    int ans; // 最终结果，即最大颜色值
    int curmax; // 当前颜色在路径中的最大出现次数
    int head[MAXN]; // 邻接表的头指针数组
    int next[MAXN]; // 邻接表的next指针数组
    int to[MAXN]; // 邻接表的to数组，存储边的终点
    int cnt=0; // 边的计数器
    int n=0; // 节点总数
    int indo[MAXN]; // 记录每个节点的入度

public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        n=colors.length(); // 获取节点总数
        memset(head,-1,sizeof(int)*n); // 初始化邻接表的头指针数组为-1
        memset(indo,0,sizeof(int)*n); // 初始化入度数组为0

        // 构建邻接表
        for(auto& edge:edges){
            next[cnt]=head[edge[0]]; // 将当前边的next指针指向头指针
            head[edge[0]]=cnt; // 更新头指针为当前边的索引
            to[cnt]=edge[1]; // 记录边的终点
            cnt++; // 边计数器递增
            indo[edge[1]]++; // 终点的入度递增
        }

        // 拓扑排序：使用队列处理入度为0的节点
        queue<int> zero;
        for(int i=0;i<n;i++){
            if(indo[i]==0){
                zero.push(i); // 将入度为0的节点加入队列
            }
        }

        while(!zero.empty()){
            int cur=zero.front(); // 取出队列中的节点
            zero.pop();
            topsortarr[cnttop++]=cur; // 将节点加入拓扑排序数组
            // 遍历当前节点的所有邻接边
            for(int ei=head[cur];ei!=-1;ei=next[ei]){
                indo[to[ei]]--; // 减少邻接节点的入度
                if(indo[to[ei]]==0){
                    zero.push(to[ei]); // 如果入度为0，加入队列
                }
            }
        }

        // 检查是否存在环：拓扑排序的节点数是否等于总节点数
        if(cnttop<n) return -1; // 存在环，返回-1

        ans=0; // 初始化最终结果为0

        // 遍历所有可能的颜色（'a'到'z'）
        for(char i='a';i<='z';i++){
            memset(dp,0,sizeof(int)*n); // 初始化dp数组为0
            curmax=0; // 初始化当前颜色的最大出现次数为0

            // 按照拓扑排序的顺序处理每个节点
            for(int k=0;k<n;k++){
                int j=topsortarr[k]; // 获取当前节点
                if(colors[j]==i){
                    dp[j]++; // 如果当前节点的颜色匹配，递增dp值
                }
                // 更新邻接节点的dp值
                for(int ei=head[j];ei!=-1;ei=next[ei]){
                    dp[to[ei]]=max(dp[j],dp[to[ei]]); // 取较大值
                }
                ans=max(ans,dp[j]); // 更新最终结果
            }
        }

        return ans; // 返回最大颜色值
    }
};